{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Regular Expression Matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #正则表达式匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;和一个字符规律&nbsp;<code>p</code>，请你来实现一个支持 <code>'.'</code>&nbsp;和&nbsp;<code>'*'</code>&nbsp;的正则表达式匹配。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'.'</code> 匹配任意单个字符</li>\n",
    "\t<li><code>'*'</code> 匹配零个或多个前面的那一个元素</li>\n",
    "</ul>\n",
    "\n",
    "<p>所谓匹配，是要涵盖&nbsp;<strong>整个&nbsp;</strong>字符串&nbsp;<code>s</code>的，而不是部分字符串。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aa\", p = \"a\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\"a\" 无法匹配 \"aa\" 整个字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aa\", p = \"a*\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 \"aa\" 可被视为 'a' 重复了一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ab\", p = \".*\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\".*\" 表示可匹配零个或多个（'*'）任意字符（'.'）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length&nbsp;&lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= p.length&nbsp;&lt;= 20</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含从&nbsp;<code>a-z</code>&nbsp;的小写字母。</li>\n",
    "\t<li><code>p</code>&nbsp;只包含从&nbsp;<code>a-z</code>&nbsp;的小写字母，以及字符&nbsp;<code>.</code>&nbsp;和&nbsp;<code>*</code>。</li>\n",
    "\t<li>保证每次出现字符&nbsp;<code>*</code> 时，前面都匹配到有效的字符</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [regular-expression-matching](https://leetcode.cn/problems/regular-expression-matching/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [regular-expression-matching](https://leetcode.cn/problems/regular-expression-matching/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aa\"\\n\"a\"', '\"aa\"\\n\"a*\"', '\"ab\"\\n\".*\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def entityParser(self, text: str) -> str:\n",
    "        # 逐个字符匹配\n",
    "        m = {\n",
    "            '&quot;':'\"',\n",
    "            '&apos;':'\\'',\n",
    "            '&gt;':'>',\n",
    "            '&lt;':'<',\n",
    "            '&frasl;':'/',\n",
    "            '&amp;':'&'\n",
    "        }\n",
    "        ans = list()\n",
    "        n = len(text)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            isMatch = False\n",
    "            if text[i] == '&':\n",
    "                for k,v in m.items():\n",
    "                    length = len(k)\n",
    "                    if text[i:i + length] == k:\n",
    "                        ans.append(v)\n",
    "                        i += length - 1\n",
    "                        isMatch = True\n",
    "                        break\n",
    "            if not isMatch:\n",
    "                ans.append(text[i])\n",
    "            i += 1\n",
    "        return ''.join(ans)\n",
    "\n",
    "        # 把&放在最后,避免被二次解析\n",
    "        return text.replace('&quot;','\"').replace('&apos;','\\'').replace('&gt;','>').replace('&lt;','<').replace('&frasl;','/').replace('&amp;','&')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def entityParser(self, text: str) -> str:\n",
    "        # py中字符串对象的str.replace方法与Jvav中replaceAll()效果相同\n",
    "        # 但这里还是采用哈希表法(字典实现)\n",
    "        rec = {\n",
    "            '&quot;': '\"',\n",
    "            '&apos;': \"'\",\n",
    "            '&amp;': \"&\",\n",
    "            \"&gt;\": '>',\n",
    "            \"&lt;\": '<',\n",
    "            \"&frasl;\": '/',\n",
    "        }\n",
    "        ans_str, n, start = [], len(text), 0\n",
    "        \n",
    "        while start<n:\n",
    "            isMatched = False\n",
    "            for l in range(1,8):\n",
    "                if text[start:start+l] in rec:\n",
    "                    ans_str.append(rec[text[start:start+l]])\n",
    "                    start += l\n",
    "                    isMatched = True\n",
    "                    break\n",
    "            if not isMatched:\n",
    "                ans_str.append(text[start])\n",
    "                start += 1\n",
    "                \n",
    "        return ''.join(ans_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for j in range(1, len(p), 2):\n",
    "            if p[j] == '*':\n",
    "                dp[0][j + 1] = dp[0][j - 1]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(p)):\n",
    "                if p[j] == s[i] or p[j] == '.':\n",
    "                    dp[i + 1][j + 1] = dp[i][j]\n",
    "                elif p[j] == '*':\n",
    "                    if p[j - 1] == s[i] or p[j - 1] == '.':\n",
    "                        dp[i + 1][j + 1] = dp[i + 1][j - 1] or dp[i][j + 1]\n",
    "                    else:\n",
    "                        dp[i + 1][j + 1] = dp[i + 1][j - 1]\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        n_ = n\n",
    "        state = [[0] * (n + 1) for i in range(m + 1)]\n",
    "        if m != n and \"*\" not in p:\n",
    "            return False\n",
    "\n",
    "        for item in p:\n",
    "            if \"*\" == item:\n",
    "                n_ -= 2\n",
    "\n",
    "        # 当s为空时 p不为空\n",
    "        if not m:\n",
    "            if not n:\n",
    "                return True\n",
    "            elif not n_:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        if n_ > m:\n",
    "            return False\n",
    "\n",
    "        # 初始化左上角\n",
    "        state[0][0] = True\n",
    "\n",
    "        # 初始化左列\n",
    "        for i in range(1, m):\n",
    "            state[i][0] = False\n",
    "\n",
    "        # 初始化顶列\n",
    "        # for j in range(1, n):\n",
    "        #     if p[j] == \"*\":\n",
    "        #         if j - 2 < 0 and n > 2:\n",
    "        #             state[0][j] = True\n",
    "        #         elif j - 2 < 0 and n <= 2:\n",
    "        #             state[0][j] = s[0] == p[0] if p[0] != '.' else True\n",
    "        #         else:\n",
    "        #             state[0][j] = state[0][j - 2]\n",
    "        #     elif p[j] == \".\":\n",
    "        #         if j > 2:\n",
    "        #             state[0][j] = False\n",
    "        #     else:\n",
    "        #         state[0][j] = s[0] == p[j] and state[0][j]\n",
    "\n",
    "        for j in range(1, n):\n",
    "            if p[j-1] == \"*\":\n",
    "                state[0][j] = state[0][j - 2]\n",
    "            else:\n",
    "                state[0][j] = False\n",
    "\n",
    "        # 递推关系\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j-1] == \".\":\n",
    "                    state[i][j] = state[i - 1][j - 1]\n",
    "                elif p[j-1] == \"*\":\n",
    "                    if p[j - 2] != s[i-1] and p[j - 2] != \".\":\n",
    "                        if j-1 < 2:\n",
    "                            state[i][j] = False\n",
    "                        else:\n",
    "                            state[i][j] = state[i][j - 2]  # 如果x前的字符和当前字符不相同，那么将x赋值为0\n",
    "                    else:\n",
    "                        state[i][j] = state[i][j - 2] or state[i - 1][j] or state[i][j - 1]\n",
    "\n",
    "                else:\n",
    "                    state[i][j] = state[i - 1][j - 1] and s[i-1] == p[j-1]\n",
    "        return state[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def Match(s, p):\n",
    "        if s == \" \" and p == \" \":\n",
    "            return True\n",
    "        if p == \" \":\n",
    "            return False\n",
    "        if s == \" \":\n",
    "            if len(p) > 1 and p[1] == '*':\n",
    "                return Match(s, p[2:])\n",
    "            return False\n",
    "        if s[0] != p[0] and p[0] != '.':\n",
    "            if len(p) > 1 and p[1] == '*':\n",
    "                return Match(s, p[2:])\n",
    "            return False\n",
    "        if len(p) > 2 and p[1] == '*':\n",
    "            return Match(s[1:], p) or Match(s[1:], p[2:]) or Match(s, p[2:])\n",
    "        return Match(s[1:], p[1:])\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for i in range(len(p) - 3):\n",
    "            if i >= len(p) - 3:\n",
    "                break\n",
    "            while (p[i] == p[i + 2] or p[i] == '.') and p[i + 1] == '*' and p[i + 3] == '*':\n",
    "                p = p[:i + 2] + p[i + 4:]\n",
    "                if i >= len(p) - 3:\n",
    "                    break\n",
    "        s = s + \" \"\n",
    "        p = p + \" \"\n",
    "        return Match(s, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isMatch(self, text, pattern):\n",
    "        memo = {}\n",
    "        def dp(i, j):\n",
    "            if (i, j) not in memo:\n",
    "                if j == len(pattern):\n",
    "                    ans = i == len(text)\n",
    "                else:\n",
    "                    first_match = i < len(text) and pattern[j] in {text[i], '.'}\n",
    "                    if j+1 < len(pattern) and pattern[j+1] == '*':\n",
    "                        ans = dp(i, j+2) or first_match and dp(i+1, j)\n",
    "                    else:\n",
    "                        ans = first_match and dp(i+1, j+1)\n",
    "\n",
    "                memo[i, j] = ans\n",
    "            return memo[i, j]\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: 'str', p: 'str') -> 'bool':\n",
    "        import re\n",
    "        i = re.match(p, s)\n",
    "        if i and i.group() == s:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            # return True if i and i.group() == s else False\n",
    "if __name__ == '__main__':\n",
    "    a = Solution().isMatch(\"ab\",\".*\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        memo = {};\n",
    "        def dp(i,j):\n",
    "            if (i, j) not in memo:\n",
    "                    if j == len(p):\n",
    "                        ans = i == len(s)\n",
    "                    else:\n",
    "                        first_match = i < len(s) and p[j] in {s[i], '.'}\n",
    "                        if j + 1 < len(p) and p[j+1] == '*':\n",
    "                            ans = dp(i, j+2) or first_match and dp(i+1, j)\n",
    "                        else:\n",
    "                            ans = first_match and dp(i+1,j+1)    \n",
    "                    memo[i,j] = ans\n",
    "            return memo[i,j];\n",
    "        return dp(0,0);\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isMatch(self, s, p):\n",
    "        memo = {}\n",
    "        def dp(i, j):\n",
    "            if (i, j) not in memo:\n",
    "                if j == len(p):\n",
    "                    ans = i == len(s)\n",
    "                else:\n",
    "                    first_match = i < len(s) and p[j] in {s[i], '.'}\n",
    "                    if j+1 < len(p) and p[j+1] == '*':\n",
    "                        ans = dp(i, j+2) or first_match and dp(i+1, j)\n",
    "                    else:\n",
    "                        ans = first_match and dp(i+1, j+1)\n",
    "\n",
    "                memo[i, j] = ans\n",
    "            return memo[i, j]\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        m = 1 if not s else len(s) + 1\n",
    "        n = 1 if not p else len(p) + 1\n",
    "\n",
    "        dp = [([False] * n) for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0:\n",
    "                    dp[i][j] = True\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = dp[i][j - 2] if p[j - 1] == \"*\" else False\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = False\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i-1][j-1] and p[j-1] in (s[i-1], \".\")) or \\\n",
    "                               (dp[i][j-2] and p[j-1] == \"*\") or \\\n",
    "                               (dp[i-1][j] and p[j-1] == \"*\" and (s[i-1] == p[j-2] or p[j-2] == \".\"))\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def _isMatch(self, s, p):\n",
    "\n",
    "        i = -1\n",
    "        j = 0\n",
    "\n",
    "        try:\n",
    "\n",
    "            while i < len(s) - 1:\n",
    "                i += 1\n",
    "\n",
    "                if s[i] == p[j] or p[j] == '.':\n",
    "                    j += 1\n",
    "\n",
    "                elif p[j] == '*':\n",
    "                    if p[j+1] in [s[i], '.']:\n",
    "\n",
    "                        if j+2 < len(p) and self._isMatch(s[i:], p[j+2:]):\n",
    "                            return True\n",
    "\n",
    "                        if i+1 >= len(s) or p[j+1] not in [s[i+1], '.']:\n",
    "                            j += 2\n",
    "\n",
    "                    else:\n",
    "                        j += 2\n",
    "                        i -= 1\n",
    "                        continue\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            while j < len(p):\n",
    "                if '*' in [p[j], p[j-1]]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        except:\n",
    "            return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    def isMatch(self, s, p):\n",
    "        \n",
    "        #if len(p) > 0 and p[0] == '*':\n",
    "        #    return False\n",
    "\n",
    "        s = s[::-1]\n",
    "        p = p[::-1]\n",
    "\n",
    "        return self._isMatch(s, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    cache = {}\n",
    "\n",
    "    def isMatch(self, s, p):\n",
    "        if (s, p) in self.cache:\n",
    "            return self.cache[(s, p)]\n",
    "        if not p:\n",
    "            return not s\n",
    "        if p[-1] == '*':\n",
    "            if self.isMatch(s, p[:-2]):\n",
    "                self.cache[(s, p)] = True\n",
    "                return True\n",
    "            if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):\n",
    "                self.cache[(s, p)] = True\n",
    "                return True\n",
    "        if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):\n",
    "            self.cache[(s, p)] = True\n",
    "            return True\n",
    "        self.cache[(s, p)] = False\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "\tdef isMatch(self, s: 'str', p: 'str') -> 'bool':\n",
    "\t\t\"\"\"\n",
    "\t\t:type s: str\n",
    "\t\t:type p: str\n",
    "\t\t:rtype: bool\n",
    "\t\t\"\"\"\n",
    "\t\tif not p: # p is NULL\n",
    "\t\t\treturn not s\n",
    "\t\t\n",
    "\t\tif len(p) == 1:\n",
    "\t\t\treturn len(s) ==1 and (s[0] == p[0] or p[0] == '.')\n",
    "\n",
    "\t\tif p[1] != '*':\n",
    "\t\t\tif not s : return False\n",
    "\t\t\treturn (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:], p[1:])\n",
    "\n",
    "\t\twhile not not s and (s[0] == p[0] or p[0] == '.') :\n",
    "\t\t\tif self.isMatch(s, p[2:]): \n",
    "\t\t\t\treturn True\n",
    "\t\t\ts = s[1:]\n",
    "\t\treturn self.isMatch(s, p[2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        #dp[i][j] 表示是否s 前i个元素能被p的前j个元素匹配\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "        \n",
    "        #p为空时候\n",
    "        if not p:\n",
    "            return not s\n",
    "        #s为空时候\n",
    "        if not s:\n",
    "            tmp = [c for c in p]\n",
    "            while tmp and tmp[-1]=='*':\n",
    "                tmp.pop()\n",
    "                tmp.pop()\n",
    "            return not tmp\n",
    "        \n",
    "        #初始化dp边界，即s的第一个字符对p的匹配\n",
    "        for j in range(n):\n",
    "            #dp[0][0]特殊判断\n",
    "            if j==0 and (s[0]==p[0] or p[0]=='.'):\n",
    "                dp[0][0] = True\n",
    "            #p[j]=='*'\n",
    "            elif j>0 and p[j]=='*':\n",
    "                if j==1:\n",
    "                    dp[0][j] = dp[0][j-1]\n",
    "                elif j>=2:\n",
    "                    if dp[0][j-2]:\n",
    "                        dp[0][j] = dp[0][j-2]\n",
    "                    elif p[j-1]==s[0] or p[j-1]=='.':\n",
    "                        tmp = j-2\n",
    "                        while tmp>0 and p[tmp]=='*':\n",
    "                            tmp-=2\n",
    "                        if tmp==-1:\n",
    "                            dp[0][j] = True\n",
    "            #p[j]与s[0]匹配\n",
    "            elif j>0 and s[0]==p[j] or p[j]=='.':\n",
    "                if p[j-1]=='*':\n",
    "                    tmp = j-3\n",
    "                    while tmp>0 and p[tmp]=='*':\n",
    "                        tmp-=2\n",
    "                    if tmp==-1:\n",
    "                        dp[0][j] = True\n",
    "            #注：p[j]与s[0]不匹配时就是False，初始状态就是False所以不用写出来了\n",
    "            \n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if s[i]==p[j] or p[j]=='.':\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j]=='*':\n",
    "                    if p[j-1]!=s[i] and p[j-1]!='.' :\n",
    "                        dp[i][j] = dp[i][j-2]\n",
    "                    elif p[j-1]==s[i] or p[j-1]=='.':\n",
    "                        dp[i][j] = (dp[i-1][j] or dp[i][j-1] or dp[i][j-2])\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        p_l = self._get_pattern_list(p)\n",
    "\n",
    "        if len(s) == 0 and len(p_l) == 1:\n",
    "            return '*' in p_l[0]\n",
    "\n",
    "        t = [[False for j in range(len(p_l)+1)] for i in range(len(s)+1)]\n",
    "        # 对i=0的条件下进行处理\n",
    "        t[0][0] = True\n",
    "\n",
    "\n",
    "        for i in range(len(s)+1):\n",
    "            for j in range(1, len(p_l)+1):\n",
    "                # 判断前i个和前j个匹配:\n",
    "                # 如果前j个和前i-1个匹配，那么需要第j个是*并且第j个和第i个匹配\n",
    "                if i > 0 and t[i-1][j] and '*' in p_l[j-1] and self._match(s[i-1], p_l[j-1]):\n",
    "                    t[i][j] = True\n",
    "                # 如果前j-1个和前i个匹配，那么需要第j个是*\n",
    "                elif t[i][j-1] and '*' in p_l[j-1]:\n",
    "                    t[i][j] = True\n",
    "                # 如果前i-1个和前j-1个匹配，但是前j个不和前i-1个匹配（那第j个肯定不可能是*)，前j-1个也不和前i个匹配\n",
    "                elif i > 0 and t[i-1][j-1] and self._match(s[i-1], p_l[j-1]):\n",
    "                    t[i][j] = True\n",
    "                \n",
    "        return t[-1][-1]\n",
    "\n",
    "    def _match(self, ch, pattern):\n",
    "        to_match_ch = pattern[0]\n",
    "        if to_match_ch == '.':\n",
    "            return True\n",
    "        else:\n",
    "            return ch == to_match_ch\n",
    "\n",
    "    def _get_pattern_list(self, p):\n",
    "        ret = []\n",
    "        i = 0\n",
    "        ch = ''\n",
    "        while i < len(p):\n",
    "            if i + 1 < len(p) and p[i+1] == '*':\n",
    "                ch = p[i:i+2]\n",
    "                i += 2\n",
    "            else:\n",
    "                ch = p[i]\n",
    "                i += 1\n",
    "            ret.append(ch)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if not p: return not s\n",
    "        if not s and len(p) == 1: return False \n",
    "\n",
    "        nrow = len(s) + 1\n",
    "        ncol = len(p) + 1\n",
    "\n",
    "        dp = [[False for c in range(ncol)] for r in range(nrow)]\n",
    "        \n",
    "        dp[0][0] = True\n",
    "        dp[0][1] = False\n",
    "        for c in range(2, ncol):\n",
    "            j = c-1\n",
    "            if p[j] == '*': dp[0][c] = dp[0][c-2]\n",
    "        \n",
    "        for r in range(1, nrow):\n",
    "            i = r-1\n",
    "            for c in range(1, ncol):\n",
    "                j = c-1\n",
    "                if s[i] == p[j] or p[j] == '.':\n",
    "                    dp[r][c] = dp[r-1][c-1]\n",
    "                elif p[j] == '*':\n",
    "                    if p[j-1] == s[i] or p[j-1] == '.':\n",
    "                        dp[r][c] = dp[r-1][c] or dp[r][c-2]\n",
    "                    else:\n",
    "                        dp[r][c] = dp[r][c-2]\n",
    "                else:\n",
    "                    dp[r][c] = False\n",
    "\n",
    "        return dp[nrow-1][ncol-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#动态规划---> dp[i][j]--> s[:i] p[:j]  i---> s // j--->n\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        \n",
    "        dp = [[False for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][0] = True \n",
    "\n",
    "        #当字符串s为空串的时候；\n",
    "        #如果当前p[j-1]为'*'，那么此时'*'的作用只能是 匹配0个前面的哪一个元素；\n",
    "        #如果当前p[j-1]不为'*'，毫无疑问，此时为False;\n",
    "\n",
    "        for j in range(2, n+1):\n",
    "            if p[j-1] == '*':\n",
    "                dp[0][j] = dp[0][j-2]\n",
    "            elif p[j-1] != '*':\n",
    "                dp[0][j] = False \n",
    "        \n",
    "        #当字符串s不为空串的时候；\n",
    "        #根据当前p[j-1]是否为'*'，分两种情况讨论:\n",
    "        #当p[j-1]不为'*'时,考虑p[j-1]，s[i-1]是否相等\n",
    "        #当p[j-1]为'*'时，处理比较麻烦：\n",
    "        #如果*匹配前面0个元素，则dp[i][j-2]；\n",
    "        #如果*匹配前面1个元素，则考虑dp[i][j-1]；\n",
    "        #如果*匹配前面多个元素，则\n",
    "\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if p[j-1] != '*':\n",
    "                    if p[j-1] == s[i-1]:\n",
    "                        dp[i][j] = dp[i-1][j-1]\n",
    "                    elif p[j-1]=='.':\n",
    "                        dp[i][j] = dp[i-1][j-1]\n",
    "                    elif p[j-1] != s[i-1]:\n",
    "                        dp[i][j] = False \n",
    "\n",
    "                elif p[j-1] == '*':\n",
    "                    dp[i][j] = dp[i][j-2] or dp[i][j-1]\n",
    "                    #'*'匹配0个或者多个前面的那一个元素\n",
    "                    #匹配前面0个，dp[i][j-2]\n",
    "                    #匹配前面1个，dp[i][j-1]\n",
    "                    \n",
    "                    # '.*'\n",
    "                    if (p[j-2] == '.') or (p[j-2] == s[i-1]):\n",
    "                        dp[i][j] = dp[i-1][j] or dp[i][j]\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if not p: return not s  # 结束条件\n",
    "\n",
    "        first_match = (len(s) > 0) and p[0] in {s[0], '.'}\n",
    "        # 先处理 `*`\n",
    "        if len(p) >=2 and p[1] == '*':\n",
    "            # 匹配0个 | 多个\n",
    "            return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))\n",
    "        else:     \n",
    "            # 处理 `.` ，匹配一个\n",
    "            return first_match and self.isMatch(s[1:], p[1:])\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isMatch(self, s: str, p: str) -> bool:\n",
    "#         self.memory = {}\n",
    "#         self.build(s, p)\n",
    "#         return self.memory[(s, p)]\n",
    "\n",
    "#     def build(self, s: str, p: str) -> bool:\n",
    "#         if not p: \n",
    "#             return not s  # 终止条件\n",
    "\n",
    "#         if (s, p) in self.memory:\n",
    "#             return self.memory[(s, p)]\n",
    "        \n",
    "#         first_match = (len(s) > 0 and p[0] in ('.', s[0]))\n",
    "#         if len(p) >= 2 and p[1] == '*':\n",
    "#             # 考虑 *， 匹配0个（前者）或者多个（后者）\n",
    "#             return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))\n",
    "#         # if p[0] == '.': 已经考虑在first_match里面\n",
    "#         # 考虑 '.' 或者 字母匹配\n",
    "#         return (first_match and self.isMatch(s[1:], p[1:]))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        boolnum=[[False for _ in range(len(p)+1)] for _ in range(len(s)+1)]\n",
    "        boolnum[0][0]=True\n",
    "        def match(s,p):\n",
    "            if p=='.':\n",
    "                return True\n",
    "            elif s==p:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        for i in range(len(s)+1):\n",
    "            for j in range(1,len(p)+1):\n",
    "                if i==0:\n",
    "                        pass\n",
    "                elif match(s[i-1],p[j-1]):\n",
    "                    boolnum[i][j]|=boolnum[i-1][j-1]\n",
    "                if p[j-1]=='*':\n",
    "                    boolnum[i][j]=boolnum[i][j-2]\n",
    "                    if i==0:\n",
    "                        pass\n",
    "                    elif match(s[i-1],p[j-2]):\n",
    "                        boolnum[i][j]|=boolnum[i-1][j]\n",
    "                \n",
    "        return boolnum[len(s)][len(p)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        return self.dp(s, 0, p, 0)\n",
    "\n",
    "    def dp(self, s: str, i: int, p: str, j: int) -> bool:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        if j == p_len:\n",
    "            return i == s_len\n",
    "\n",
    "        if i == s_len:\n",
    "            if (p_len - j) % 2 == 1:\n",
    "                return False\n",
    "            for x in range(j + 1, p_len, 2):\n",
    "                if p[x] != '*':\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        if s[i] == p[j] or p[j] == '.':\n",
    "            if j < p_len - 1 and p[j + 1] == '*':\n",
    "                flag = self.dp(s, i + 1, p, j) or self.dp(s, i, p, j + 2)\n",
    "            else:\n",
    "                flag = self.dp(s, i + 1, p, j + 1)\n",
    "        else:\n",
    "            if j < p_len - 1 and p[j + 1] == '*':\n",
    "                flag = self.dp(s, i, p, j + 2)\n",
    "            else:\n",
    "                return False\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        ns, np = len(s), len(p)\n",
    "        dp = [[False] * (ns + 1) for _ in range(np + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(np):\n",
    "            if p[i] == '*':\n",
    "                dp[i + 1][0] = dp[i - 1][0]\n",
    "\n",
    "        for i in range(np):\n",
    "            for j in range(ns):\n",
    "                if p[i] not in ['.', '*']:\n",
    "                    dp[i + 1][j + 1] = (p[i] == s[j] and dp[i][j])\n",
    "                elif p[i] == '.':\n",
    "                    dp[i + 1][j + 1] = dp[i][j]\n",
    "                else:\n",
    "                    if dp[i - 1][j + 1]:\n",
    "                        dp[i + 1][j + 1] = True\n",
    "                        continue\n",
    "\n",
    "                    prev = p[i - 1]\n",
    "                    for k in range(j, -1, -1):\n",
    "                        if prev == '.' or s[k] == prev:\n",
    "                            if dp[i - 1][k]:\n",
    "                                dp[i + 1][j + 1] = True\n",
    "                                break\n",
    "                        else:\n",
    "                            break\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        import re\n",
    "        if re.fullmatch(p, s):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        sLen, pLen = len(s), len(p)\n",
    "        memo = {}\n",
    "        def dp(i, j):\n",
    "            if j == pLen: return i == sLen\n",
    "            if i == sLen:\n",
    "                if (pLen - j) % 2: return False\n",
    "                for k in range(j+1,pLen, 2):\n",
    "                    if p[k] != \"*\": return False\n",
    "                return True\n",
    "            if (i, j) in memo: return memo[(i, j)]\n",
    "            print(i, j)\n",
    "            if s[i] == p[j] or p[j] == '.':\n",
    "                if j < pLen - 1 and p[j+1] == '*':\n",
    "                    memo[(i, j)] = dp(i+1, j) or dp(i, j+2)\n",
    "                else:\n",
    "                    memo[(i, j)] = dp(i+1, j+1)\n",
    "            else:\n",
    "                if j < pLen - 1 and p[j+1] == '*':\n",
    "                    memo[(i, j)] = dp(i, j + 2)\n",
    "                else:\n",
    "                    memo[(i, j)] = False\n",
    "            return memo[(i, j)]\n",
    "        return dp(0, 0)                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 10. 正则表达式匹配\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dfs(s, p):\n",
    "            if s == \"\" and p == \"\":\n",
    "                return True\n",
    "            elif p == \"\":\n",
    "                return False\n",
    "            elif s == \"\":\n",
    "                size = len(p)\n",
    "                if size % 2 == 1: return False\n",
    "                for i in range(1, size, 2):\n",
    "                    if p[i] != \"*\": return False\n",
    "                return True\n",
    "            else:\n",
    "                if p[0] == \".\":\n",
    "                    if len(p) > 1 and p[1] == \"*\":\n",
    "                        if len(p) == 2: return True\n",
    "                        size = len(s)\n",
    "                        for i in range(size+1):\n",
    "                            if dfs(s[i:], p[2:]): return True\n",
    "                        return False\n",
    "                    else:\n",
    "                        return dfs(s[1:], p[1:])\n",
    "                else:\n",
    "                    if len(p) > 1 and p[1] == \"*\":\n",
    "                        if dfs(s, p[2:]): return True\n",
    "                        i = 0\n",
    "                        size = len(s)\n",
    "                        while i < size and p[0] == s[i]:\n",
    "                            if dfs(s[i+1:], p[2:]): return True\n",
    "                            i = i + 1\n",
    "                        return False\n",
    "                    else:\n",
    "                        if s[0] == p[0]:\n",
    "                            return dfs(s[1:], p[1:])\n",
    "                        else:\n",
    "                            return False\n",
    "        return dfs(s, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if not p:\n",
    "            return not s\n",
    "        first_match = bool(s) and p[0] in {'.', s[0]}\n",
    "        if len(p)>=2 and p[1]=='*':\n",
    "            return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)\n",
    "        else:\n",
    "            return first_match and self.isMatch(s[1:], p[1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "\n",
    "        def matches(i: int, j: int) -> bool:\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        f = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = True\n",
    "        for i in range(m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    f[i][j] |= f[i][j - 2]\n",
    "                    if matches(i, j - 1):\n",
    "                        f[i][j] |= f[i - 1][j]\n",
    "                else:\n",
    "                    if matches(i, j):\n",
    "                        f[i][j] |= f[i - 1][j - 1]\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        def matchChar(i,j):\n",
    "            if s[i]==p[j]:\n",
    "                return True\n",
    "            if p[j]=='.':\n",
    "                return True\n",
    "            return False\n",
    "        m,n=len(s),len(p)\n",
    "        dp=[[False]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0]=True\n",
    "        for j in range(2,n+1):\n",
    "            if p[j-1]=='*' and dp[0][j-2]:\n",
    "                dp[0][j]=True\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if dp[i-1][j-1] and matchChar(i-1,j-1):\n",
    "                    dp[i][j]=True\n",
    "                if dp[i][j] and j<=n-1 and p[j]=='*':\n",
    "                    dp[i][j+1]=True\n",
    "                if dp[i][j] and j<n-1 and p[j+1]=='*':\n",
    "                    dp[i][j+2]=True\n",
    "                if p[j-1]=='*':\n",
    "                    #if i>=2 and dp[i-2][j-2]:\n",
    "                    #    dp[i-2][j]=True\n",
    "                    if i>1 and dp[i-1][j-1]==True:\n",
    "                        #dp[i-1][j]=True\n",
    "                        for k in range(i,m+1):\n",
    "                            if matchChar(k-1,j-2):\n",
    "                                dp[k][j]=True\n",
    "                            else:\n",
    "                                break\n",
    "        return dp[m][n]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        def matchc(s,slist):\n",
    "            for i in slist:\n",
    "                if s != i:\n",
    "                    return False\n",
    "            return True\n",
    "        def MatchVoid(p):\n",
    "            j = 0\n",
    "            if not p:\n",
    "\n",
    "                return True\n",
    "            elif len(p) % 2 == 1 or p[0] == '*':\n",
    "                return False\n",
    "            else:\n",
    "                if p[1] == \"*\" and len(p) == 2 and p[0] != \"*\":\n",
    "\n",
    "                    return True\n",
    "                elif p[1] == \"*\":\n",
    "                    return MatchVoid(p[2:])\n",
    "                else:\n",
    "                    return False\n",
    "        i = 0\n",
    "        if p[0] == '*':\n",
    "            return False\n",
    "        while p[i] != \"*\":\n",
    "            if i == len(s) - 1 and i == len(p) -1:\n",
    "                return p[i] == s[i] or p[i] == '.'\n",
    "            elif i == len(p) -1:\n",
    "                return False\n",
    "            if p[i+1] == '*' and i+2 < len(p):\n",
    "                if self.isMatch(s[i:], p[i+2:]) == True:\n",
    "                    return True\n",
    "            if i == len(s) - 1 and (p[i] == s[i] or p[i] == '.'):\n",
    "                return MatchVoid(p[i+1:]) or p[i+1] == '*' and i + 1 == len(p) or p[i+1] == '*' and MatchVoid(p[i+2:])\n",
    "            elif p[i] != '.' and p[i] != s[i]:\n",
    "                return False\n",
    "            i += 1\n",
    "        cur = s[i-1]\n",
    "        cur_index = i\n",
    "        while cur_index < len(p) - 2:\n",
    "            if p[cur_index+1] == p[cur_index-1] and p[cur_index+2] == '*':    \n",
    "                cur_index += 2\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        if p[i-1] != '.':\n",
    "            if cur_index == len(p)-1:\n",
    "                return matchc(s[i-1], s[i:])\n",
    "            if self.isMatch(s[i-1:], p[cur_index+1:]) == True: \n",
    "                return True\n",
    "            \n",
    "\n",
    "            i = i - 1\n",
    "            while s[i] == cur:\n",
    "                if i == len(s) - 1:\n",
    "                    return MatchVoid(p[cur_index+1:])\n",
    "                if self.isMatch(s[i+1:], p[cur_index+1:]) == True:\n",
    "                    return True\n",
    "                i += 1\n",
    "            return False\n",
    "        else:\n",
    "            if cur_index == len(p)-1:\n",
    "                return True\n",
    "            \n",
    "            i = i - 1\n",
    "            while i <= len(s) - 1:\n",
    "                if self.isMatch(s[i:], p[cur_index+1:]) == True: \n",
    "                    print((s[i:], p[cur_index+1:]))\n",
    "                    return True\n",
    "                i += 1\n",
    "            \n",
    "            return MatchVoid(p[cur_index+1:])\n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        slen = len(s)\n",
    "        plen = len(p)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == slen and j == plen : return True\n",
    "            if i > slen or j >= plen: return False\n",
    "\n",
    "            # print(i, j)\n",
    "            if i == slen  :\n",
    "                if j + 1 < plen and p[j + 1] =='*':\n",
    "                    return dfs(i, j + 2)\n",
    "                return False\n",
    "\n",
    "            if j + 1 < plen and p[j + 1] =='*':\n",
    "                if s[i] == p[j] or p[j] == '.':\n",
    "                    return dfs(i + 1, j) or dfs(i, j + 2)\n",
    "                return dfs(i, j + 2)\n",
    "\n",
    "            if s[i] == p[j] or p[j] == '.':\n",
    "                return dfs(i + 1, j + 1)\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        slen = len(s)\n",
    "        plen = len(p)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == slen and j == plen : return True\n",
    "            if i > slen or j >= plen: return False\n",
    "\n",
    "            # print(i, j)\n",
    "            if i == slen  :\n",
    "                if j + 1 < plen and p[j + 1] =='*':\n",
    "                    return dfs(i, j + 2)\n",
    "                return False\n",
    "\n",
    "            if j + 1 < plen and p[j + 1] =='*':\n",
    "                if s[i] == p[j] or p[j] == '.':\n",
    "                    return dfs(i + 1, j) or dfs(i + 1, j + 2) or dfs(i, j + 2)\n",
    "                return dfs(i, j + 2)\n",
    "\n",
    "            if s[i] == p[j] or p[j] == '.':\n",
    "                return dfs(i + 1, j + 1)\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution: \n",
    "    def isMatch(self, s: str, p: str) -> bool: \n",
    "        s_len, p_len = len(s), len(p)\n",
    "        match_table = [[False] * (p_len+1) for _ in range(s_len+1)]\n",
    "        match_table[0][0] = True\n",
    "        \n",
    "        for i in range(s_len+1):\n",
    "            for j in range(1,p_len+1):\n",
    "                if p[j-1] == '*':\n",
    "                    match_table[i][j] = match_table[i][j-2] | (match_table[i-1][j] & (p[j-2] in [s[i-1], '.']) )  \n",
    "                else:\n",
    "                    match_table[i][j] = (match_table[i-1][j-1] & (p[j-1] in [s[i-1], '.']) )  \n",
    "                \n",
    "        return match_table[s_len][p_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        \"\"\"\n",
    "        注意边界情况的处理\n",
    "        \"\"\"\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [[False] * (n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2,n+1,2):  # dp[0][j] 表示匹配空字符串，a*组合可以匹配空字符串\n",
    "            dp[0][j] = p[j-1] == '*' and dp[0][j-2]\n",
    "        \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if p[j-1] == '.' or p[j-1] == s[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j-1] == '*' and j > 1:\n",
    "                    dp[i][j] =  dp[i][j-2] or (p[j-2] == '.' or p[j-2] == s[i-1]) and dp[i-1][j]\n",
    "        \n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [[False for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n+1, 2):\n",
    "            if p[j-1] == \"*\":\n",
    "                dp[0][j] = dp[0][j-2]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if p[j-1] == \"*\":\n",
    "                    if dp[i-1][j] and p[j-2]==s[i-1]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j] and p[j-2]==\".\":\n",
    "                        dp[i][j] = True\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-2]\n",
    "                    print(i, j, dp[i][j])\n",
    "                else:\n",
    "                    if s[i-1]==p[j-1] or p[j-1]==\".\":\n",
    "                        dp[i][j] = dp[i-1][j-1]\n",
    "                    print(i, j, dp[i][j])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        #i..len(s)-1,j..len(p)-1 匹配吗？\n",
    "        @cache  #加缓存，可以用map做\n",
    "        def f(i,j):\n",
    "            #都匹配完了\n",
    "            if i==len(s) and j==len(p):\n",
    "                return True\n",
    "            #p匹配完了，s还没匹配完\n",
    "            if j==len(p):\n",
    "                return False\n",
    "            #s匹配完了，看看p后面能不能用*消除\n",
    "            if i==len(s) and j+1<len(p) and p[j+1]==\"*\":\n",
    "                return f(i,j+2)\n",
    "            #s匹配完了，p后面也不能用*消除\n",
    "            if i==len(s):\n",
    "                return False\n",
    "            #p,s都没匹配完，i+1是*，分情况\n",
    "            if j+1<len(p) and p[j+1]==\"*\":\n",
    "                #    p[i]*匹配0个                    p[i]*匹配1，2，...n个\n",
    "                return f(i,j+2) or ((s[i]==p[j] or p[j]==\".\") and f(i+1,j))\n",
    "            #p,s都没匹配完，i+1不是*\n",
    "            else:\n",
    "                #一种情况，直接匹配\n",
    "                return (s[i]==p[j] or p[j]==\".\") and f(i+1,j+1)\n",
    "        #返回i..len(s)-1,j..len(p)-1 匹配\n",
    "        return f(0,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
